% Appendix X



\chapter{Old Document 1}

%----------------------------------------------------------------------------------------

\section{Experiment}
The objective of the Master's thesis is to develop a method to allocate robots to dynamic and spatially distributed tasks.

In order to develop such kind of method a suitable experimental setup must be implemented.

The experiment will involve 20 e-puck robots starting from a predefined area (nest) and 32 booths, 25 of them actually requiring the presence of a robot, distributed as follows:
\begin{itemize}
\item \bf{4} clusters of \bf{8} booths each.
\end{itemize}

The \emph{number of booths} is \textbf{greater} than the \emph{number of e-pucks} in order to be able to test different configurations (i.e. task demands for each cluster).
Furthermore, it is assumed that the number of robots is not sufficient to perform a complete coverage of the environment.

The tasks are \textbf{sporadic} (i.e. does not occur periodically), \textbf{atomic} (i.e. it cannot be suspended and later resumed) in order to test the capability of the swarm to dynamically adapt to changes in configurations instead of learning periodic patterns.

%The presence of cluster having different sizes is intended to test the capability of the robots to choose and allocate themselves to the 

The experiment is articulated into two distinct phases:

\paragraph{Phase A}
\begin{center}
\begin{tabular}{| c | c | c |}
  \hline
  \bf{Cluster} & \bf{Booths} & \bf{Request} \\
  \hline
  1 & 8 & 7 \\
  2 & 8 & 5 \\
  3 & 8 & 8 \\
  4 & 8 & 5 \\
  \hline  
\end{tabular}
\captionof{table}{Phase A configuration}
\end{center}
In the first one, the robots must react to the initial configuration and allocate themselves to the different clusters.

\paragraph{Phase B}
\begin{center}
\begin{tabular}{| c | c | c |}
  \hline
  \bf{Cluster} & \bf{Booths} & \bf{Request} \\
  \hline
  1 & 8 & 4 \\
  2 & 8 & 8 \\
  3 & 8 & 6 \\
  4 & 8 & 7 \\
  \hline  
\end{tabular}
\captionof{table}{Phase B configuration}
\end{center}
In the second one, from the uneven task distribution of the first phase the tasks will be uniformly distributed among the octagonal clusters.
Between the two aforementioned phases there will be a transient period to allow the dispersion of the robots before the new allocation.


\subsection{E-pucks}
The e-puck controller must implement functionalities to deal with the common practical problems such as obstacle avoidance, procedures to enter and exit the booths, phototaxis and cluster exploration.

In addition to those basic behaviors the controller should also implement a baseline allocation strategy.

Since robots have no a priori knowledge about the clusters sizes and occupation, the basic idea of the strategy is that robot should gather information about them whenever they have the possibility to do it.

That is, everytime either a free or an occupied booth is seen, the robot will direct towards it to be able to update its information about the cluster.

The information exchange is implemented by means of the loop function, even though different possibile implementations can be foreseen (e.g. counting of the empty booths, presence of an information booth).

If at least one booth in the cluster is free, the robot will decide to allocate itself to that position, otherwise it will leave the cluster.
The decision to abandon the cluster is implemented by ignoring the sensed information from the camera and performing a random walk for a certain amount of time (perhaps with a decreasing probability to keep performing the blind walk).

In analogy with the "perturbation" operation in iterated local search, this will allow the robot to restart exploration instead of focusing on exploitation.

The same behavior applies when the robot has terminated its abstracted working session inside of the booth.

The basic greedy strategy will involve allocation to the first task sensed and still not undertaken by any other agent, without any form of recruitment or communication among robots.

The robots store only information concerning the previously visited cluster, hence they do not have global information about all the clusters.

 

\subsection{TAM}
The task are represented by spatially distributed booths.

The robots must reach and enter the booth to undertake the corresponding working activity.


\subsubsection{Logical FSM}


%The tasks' duration in time follows an exponential distribution with mean $\frac{1}{\lambda} = 20$


\section{Experiment results}

\subsection{Metric}
\subsubsection{Allocation quality}
The occupation $O_i$ of a cluster $i$ is defined as: 
\begin{equation}
O_i = R_i - E_i
\end{equation}
where $R_i$ is the number of booths requesting the presence of a robot and $E_i$ is the number of empty booths requesting the presence of a robot.

Note that $ E_i \le R_i$.

Agents are able to compute locally the metric by means of the information exchange with the cluster and try to maximize the occupation by allocating themselves to the group $k$ such that $O_k = \min_i O_i$.

During the experiment, the maximum integrated error will be computed as follows:
\begin{equation}
MEI = \int_{0}^{t} \max_{i} (R_i(t) - O_i(t)) dt =  \int_{0}^{t} \max_{i} (E_i(t)) dt
\end{equation}

\paragraph{Optimal allocation quality}
\begin{equation}
MEI_{best} = \lfloor \frac{\sum_{i=0}^{C}R_i - n}{C} \rfloor + 1
\end{equation}

where $R_i$ is the request of each cluster, $C$ is the number of clusters and $n$ the number of the robots.

\subsubsection{Allocation speed}
In order to measure the allocation speed, the time required to reach the following allocation level will be also computed:
\begin{itemize}
\item 25\% of the request satisfied in each cluster
\item 50\% of the request satisfied in each cluster
\item 75\% of the request satisfied in each cluster
\item (100\% of the request satisfied in each cluster)
%Possibily \item X\% of the request satisfied in each cluster
\end{itemize}
%How to deal with group size? Weight

%Integrate across time.

%Utilization
%Percentage of occupied booth in the cluster with respect to the total number requesting the presence of a robot.

%Throughput
%The number of processes that are completed per time unit?

%Waiting time
% Sum of the waiting time of the single booths.
% Waiting time for a single booth = time spent waiting for a robot

%service time
%The amount of CPU time that a process will need before it either finishes or voluntarily exits the CPU, such as to wait for input / output.


%response time
%The time from first submission of the process until the first running.

\section{Research questions}
\subsection{How to deal with the following problems?}
The choice of having less robots than booths has some important implications:
\begin{itemize}
\item Area coverage methods with or without comunication should be the main part of the proposed method in order to disperse the robots in the environment.

\item Area coverage may not be the best solution since the goal of the method is to cover area and not allocate proportionally to the requests
%\item The presence of homogeneous tasks and homogeneous robots suggests that there is no need for specialization and/or division of labour (that is, each robot is able to undertake any of the proposed tasks).
\item Threshold model, in a similar way to the Mailmen article:
\begin{itemize}
\item Specialize the robot on a cluster
\item Instead of global information, only local information is available.
\end{itemize}
\item The size of the arena is crucial to determine the need for a recruiting behavior:
\begin{itemize}
\item Given the occupation as metric, there is a tradeoff between the cluster occupation and the number of robots that choose to recruit other robots, thus not improving the measured metric
\item The effectiveness of a recruiting behavior depends on the size of the arena and on the number of robots.
\end{itemize}
\item A recruiting behavior requires the use of:
\begin{itemize}
\item Encoders - To perform odometry to keep track of the position of the last visited cluster.
\item Range and Bearing sensors - To exchange information among robots
\end{itemize}
\item A beacon that can be seen by all the robots may be used to direct the robots instead of using odometry (all the positions can be given with respect to the beacon.)
\end{itemize}

\subsection{Proposals}

\begin{itemize}
\item Increase the number of robots to meet the number of requests, in order to have a lower bound for the measured metric equal to zero.
\item Diffusion method to share the knowledge about the cluster requests before proceeding to allocation.
\item Article \cite{hsieh2008biologically} approaches a similar problem, but:
\begin{itemize}
\item The environment is static.
\item The redistribution of the robots is computed off-line and then distributed among the robots.
\item The topology of the environment is globally known.
\end{itemize}
\end{itemize}

\subsubsection{Diffusion/Chain formation}
\begin{minipage}{.45\textwidth}
\centering
\paragraph{Pros}
\begin{itemize}
\item Connectivity
\item Continuous information exchange
\end{itemize}
\end{minipage}%
\hspace{1.5cm}
\begin{minipage}{.45\textwidth}
\centering
\paragraph{Cons}
\begin{itemize}
\item Depends on the quality of the Range and Bearing system
\item Robots in the chain are not allocated to task
\item Scalability depends on the size of the area and the robots
\end{itemize}
\end{minipage}

\subsubsection{Recruiting behavior}
\begin{minipage}{.45\textwidth}
\centering
\paragraph{Pros}
\begin{itemize}
\item Few robots are not allocated to the tasks
\item Scalability
\end{itemize}
\end{minipage}%
\hspace{1.5cm}
\begin{minipage}{.45\textwidth}
\centering
\paragraph{Cons}
\begin{itemize}
\item The clusters' position must be known by the recruiter at any time, otherwise:
\begin{itemize}
  \item The exploration time will have a strong influence on the performance of the method
  \item The recruiter could get lost thus becoming ineffective.
\end{itemize}
\item The size of the arena has a great impact on the recruiting behavior.

The larger the arena, the higher the likelihood that the information carried by the recruited is outdated, thus useless.
\item Scalability depends on the size of the area and the robots
\end{itemize}
\end{minipage}

\section{Related literature}
\subsection{Biologically inspired redistribution of a swarm of robots among multiple sites}
\subsubsection{Background}
Mainly two sources:
\begin{itemize}
  \item \emph{Temnothorax albipennis} ants tandem run: Recruiting behavior to choose among two nests.
        \begin{quotation}
    "During the selection process ants make a transition spontaneously between different allegiances at well defined and experimentally measurable rates. The pattern of transition rates, which ultimately determine the average
propensity of individual ants to switch behaviors, ensures that the higher quality nest is generally chosen and that no ants are stranded in the worse nest."
  \end{quotation}
  \item Article \cite{halasz2007dynamic} : Modeling and extension of the ants' behavior to multiple ants and multiple nests, based on transition rates.
\end{itemize}
\subsubsection{Problem statement}
\begin{itemize}
  \item $N$ agents to be distributed among $M$ sites
  \item $x_i(t) = \frac{n_i(t)}{\sum_j\bar{n_j}}$ - Fraction of agents at site $i$
  \item $\bar{x_i} = \bar{n_i}{\sum_j\bar{n_j}}$ - Target configuration at site $i$
  \item $\mathcal{G(V,E)}$ - Topology of the enviroment : Nodes ($\mathcal{V}$) and one-way connections among them ($\mathcal{E}$)
  \item $k_{ij}$ - Transition probability per unit of time from site $i$ to site $j$
  \item $\phi_{ij}$ - Flux of robots from site $i$ to site $j$
  \item $\tau_{ij}$ - Travel time from site $i$ to site $j$
\end{itemize}
\subsubsection{Methodology}
\begin{itemize}
  \item \textbf{Baseline strategy:} $ \mathbf{K} = 
        \begin{cases}
        \mathbf{K}_{ij} = k_{ji}  & i \ne j \\
        \mathbf{K}_{ij} = -\sum_{j=1}^M k_{ji}  & i = j\\
        \end{cases}$ 
        determines the transition probabilities that trigger the robot deployment from one site to another.
  \item \textbf{Quorum strategy:} Each site has its quorum value $q_i$. If the current occupation $x_i(t)$ is above the quorum then one of the outgoing transitions rates from that node are multiplied of a coefficient $\alpha$ until the occupation goes back again below quorum.
  \item Metropolis optimization (Landau and Binder 2000) is used with the entries of $\mathbf{K}$ as the optimization variables.
  \item The model is then implemented with Poisson transitions controlled by fixed transition rates.
\end{itemize}

\subsubsection{Discussion}
\begin{itemize}
\item \textbf{Towards a physical implementation:} Real-world non-linear effects on the sensors and actuators have not been modeled. 
The robots move towards another site according to a Poisson process with transition rates determined according to  $\mathbf{K}$ (baseline) or according to the estimation of the relation between the current occupation and the quorum value based on the encounter rate (quorum).
In both cases, the robots compute the time at which they should leave the site to move towards another.
\item \textbf{Strict hypothesis:} The topology of the environment is known (global information) and the transitions rate are pre-computed than distributed to the agents.
\item \textbf{Under the aforementioned assumptions}, this bio-inspired method is able to perform a redistribution of the agents among sites from an initial state to a desired state.
\item \textbf{Differences with respect to the current problem:} The redistribution must be done in real-time without global information concerning the topology of the environment or the transition rates.
\end{itemize}

\chapter{Old documents 2}
The thesis is developed in the framework of {\bf swarm robotics}, thus using an high number of autonomous agents with local sensing and limited communtication capabilities.
The redundancy of relatively simple robots ensures the ability to cope with the loss of individuals (i.e. \emph{robustness}) and allows for a general \emph{flexibility} of the system, which can be adapted to a broad spectrum of different environments and activities.
The lack of global knowledge requires local coordination and self-organization to undertake complex global tasks.
This contributes to the \emph{scalability} of the system, since no central control system, whose complexity will be dependant of the size of the swarm, is impemented.

The development of the thesis will principally be done by means of {\bf simulations}, without focusing on the issues related to real robots implementation.
The simulation of the robots and their environment is made possible by ARGoS \cite{Pinciroli:SI2012}, a state-of-the-art, open source robot simulator designed for the simulation of large heterogeneous swarms of robots, mainly designed and developed by Carlo Pinciroli and his colleagues from the IRIDIA-ULB lab.

The simulated {\bf hardware} consists of e-puck robots and TAMs.
E-pucks \cite{Mondada2006} are modular, robust and open-source wheeled robots, that can sense the enviroment by means of a color camera and interact among them by means of a local wireless communication system.
%
On the other hand, the Task Abstraction Module (TAM)~\cite{Brutschy:TechRep:2010} is a physical device allowing the abstraction of a task.
It consists of an U-shaped metallic structure where a single robot could enter.
The TAM is able to detect the presence of an entity and interact with it by means of colored LEDs.

%The robot are assumed to be deployed either randomly or in predefined initial configuration (i.e. in a nest) in an unknown but closed environment.
In our {\bf scenario}, the spatially distributed tasks are represented by means of TAM clusters that are detectable by the robots during their exploration.
Robots have no a priori knowledge regarding the topology of the environment or the clusters number and size.

The main {\bf goal} of the method is to allow the swarm to dynamically adapt its spatial configuration to respond to the needs of the environment, modeled by the TAM clusters states (e.g. number of devices currently occupied or currenty requiring the presence of a robot).

Even though the use of TAM introduces an high level of abstraction in the development process, making it distant from a real life use case, I foresee some {\bf possible applications} for the method.
%
For example, by considering the clusters as aggregates of houses, one could think of the method as a possible solution of the problem of allocating resources (e.g. police patrols, garbage trucks, ambulances) while respecting some constraints (e.g. at least one resource per cluster, priority of a group over another).
The self-organization and cooperation achieved by the agents will allow the swarm to face the changes in the demands by each cluster across time.


\section{Current state of the thesis}
Until now, my work has been focused mainly on {\bf deepening my knowledge} of swarm robotics literature by researching the state of the art concerning the different sub problems related to the development of the method, namely area coverage and task allocation.
Figure \ref{fig:1} summarizes the main results obtained in this phase.

\begin{center}
\begin{tikzpicture}
  \path[mindmap,concept color=black,text=white]
    node[concept] {Spatial Allocation in Swarm Robotics}
    [clockwise from=0]
    child[concept color=orange] {
      node[concept] {Area coverage}
      [clockwise from=90]
      child { node[concept] {Virtual spring mesh} }
      child { node[concept] {Artificial potential field} }
      child { node[concept] {Facility location} }
    }  
    child[concept color=blue] {
      node[concept] {Sensor information coverage}
      [clockwise from=-30]
      child { node[concept] {Information-theoretic approach} }
    }
    child[concept color=green!50!black] { 
    node[concept] {Task allocation} };
\end{tikzpicture} 
\captionof{figure}{State of the art summary}\label{fig:1}
\end{center}

Furthermore, I got experienced with the {\bf software tools} required for the development of the thesis.
I learned how to structure and implement a controller for the devices I have to simulate using ARGoS (E-puck and TAM).
%
Some time has been dedicated to the understanding of the structure of the simulator, in order to be able to take advantage of the useful features offered.
%(e.g. the use of a loop function to gather data from the simulated enviroment for further analysis).

Last but not least, I am currently developing a naive controller to deploy the robots in the clusters, which will serve as a basis for the actual method and which will provide a baseline for performance comparisons.


\begin{table} % Add the following just after the closing bracket on this line to specify a position for the table on the page: [h], [t], [b] or [p] - these mean: here, top, bottom and on a separate page, respectively
\centering % Centers the table on the page, comment out to left-justify
\begin{tabular}{l c c c c c} % The final bracket specifies the number of columns in the table along with left and right borders which are specified using vertical bars (|); each column can be left, right or center-justified using l, r or c. To specify a precise width, use p{width}, e.g. p{5cm}
\toprule % Top horizontal line
& \multicolumn{5}{c}{Growth Media} \\ % Amalgamating several columns into one cell is done using the \multicolumn command as seen on this line
\cmidrule(l){2-6} % Horizontal line spanning less than the full width of the table - you can add (r) or (l) just before the opening curly bracket to shorten the rule on the left or right side
Strain & 1 & 2 & 3 & 4 & 5\\ % Column names row
\midrule % In-table horizontal line
GDS1002 & 0.962 & 0.821 & 0.356 & 0.682 & 0.801\\ % Content row 1
NWN652 & 0.981 & 0.891 & 0.527 & 0.574 & 0.984\\ % Content row 2
PPD234 & 0.915 & 0.936 & 0.491 & 0.276 & 0.965\\ % Content row 3
JSB126 & 0.828 & 0.827 & 0.528 & 0.518 & 0.926\\ % Content row 4
JSB724 & 0.916 & 0.933 & 0.482 & 0.644 & 0.937\\ % Content row 5
\midrule % In-table horizontal line
\midrule % In-table horizontal line
Average Rate & 0.920 & 0.882 & 0.477 & 0.539 & 0.923\\ % Summary/total row
\bottomrule % Bottom horizontal line
\end{tabular}
\caption{Table caption text} % Table caption, can be commented out if no caption is required
\label{tab:template} % A label for referencing this table elsewhere, references are used in text as \ref{label}
\end{table}

A reference to Table \ref{tab:template}.

\section{Thesis Evaluation}
\subsection{Remarks}
\begin{itemize}
  \item \textbf{State-of-the-art analysis:} Describe where the current work can be placed with respect to the existing literature on the subject.
  \item \textbf{Real-life application:} Have solutions for the problem already been developed? If so, what are the performances of the presented method with respect to those solutions
  \item \textbf{Bibliography:} Pay attention to the details in the bibliography. Cite correctly references.
  \item \textbf{Formal notation in the Thesis}
  \item \textbf{Presentation:} Focus on the ideas, not on the details. It lasts 20-30 minutes.
  \item Pay attention to the following components, ordered by priority:
  		\begin{enumerate}
  			\item Figures
  			\item Tables
  			\item Captions
			\item Abstract  			
  			\item Titles
  			\item Chapter headers
  			\item Introduction
  			\item Conclusion
  			\item Rest of thesis
  		\end{enumerate}
  \item \textbf{Intellectual honesty!}
  \item Multiple representation of data are interesting if justified.
  \item \textbf{Be prepared to the question: What is your contribution?}
\end{itemize}